home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 60 / IOPROG_60.ISO / soft / c++ / gsl-1.1.1-setup.exe / {app} / src / eigen / herm.c next >
Encoding:
C/C++ Source or Header  |  2002-04-18  |  4.7 KB  |  182 lines
  1. /* eigen/herm.c
  2.  * 
  3.  * Copyright (C) 2001 Brian Gough
  4.  * 
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or (at
  8.  * your option) any later version.
  9.  * 
  10.  * This program is distributed in the hope that it will be useful, but
  11.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  * General Public License for more details.
  14.  * 
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. #include <config.h>
  21. #include <stdlib.h>
  22. #include <gsl/gsl_math.h>
  23. #include <gsl/gsl_vector.h>
  24. #include <gsl/gsl_matrix.h>
  25. #include <gsl/gsl_linalg.h>
  26. #include <gsl/gsl_eigen.h>
  27.  
  28. /* Compute eigenvalues of complex hermitian matrix using reduction to
  29.    real symmetric tridiagonal form, followed by QR iteration with
  30.    implicit shifts.
  31.  
  32.    See Golub & Van Loan, "Matrix Computations" (3rd ed), Section 8.3 */
  33.  
  34. #include "qrstep.c"
  35.  
  36. gsl_eigen_herm_workspace * 
  37. gsl_eigen_herm_alloc (const size_t n)
  38. {
  39.   gsl_eigen_herm_workspace * w ;
  40.  
  41.   if (n == 0)
  42.     {
  43.       GSL_ERROR_NULL ("matrix dimension must be positive integer", GSL_EINVAL);
  44.     }
  45.   
  46.   w = (gsl_eigen_herm_workspace *) malloc (sizeof(gsl_eigen_herm_workspace));
  47.  
  48.   if (w == 0)
  49.     {
  50.       GSL_ERROR_NULL ("failed to allocate space for workspace", GSL_ENOMEM);
  51.     }
  52.  
  53.   w->d = (double *) malloc (n * sizeof (double));
  54.  
  55.   if (w->d == 0)
  56.     {
  57.       GSL_ERROR_NULL ("failed to allocate space for diagonal", GSL_ENOMEM);
  58.     }
  59.  
  60.   w->sd = (double *) malloc (n * sizeof (double));
  61.  
  62.   if (w->sd == 0)
  63.     {
  64.       GSL_ERROR_NULL ("failed to allocate space for subdiagonal", GSL_ENOMEM);
  65.     }
  66.  
  67.   w->tau = (double *) malloc (2 * n * sizeof (double));
  68.  
  69.   if (w->tau == 0)
  70.     {
  71.       GSL_ERROR_NULL ("failed to allocate space for tau", GSL_ENOMEM);
  72.     }
  73.  
  74.   w->size = n;
  75.  
  76.   return w;
  77. }
  78.  
  79. void
  80. gsl_eigen_herm_free (gsl_eigen_herm_workspace * w)
  81. {
  82.   free (w->tau);
  83.   free (w->sd);
  84.   free (w->d);
  85.   free(w);
  86. }
  87.  
  88. int
  89. gsl_eigen_herm (gsl_matrix_complex * A, gsl_vector * eval,
  90.                      gsl_eigen_herm_workspace * w)
  91. {
  92.   if (A->size1 != A->size2)
  93.     {
  94.       GSL_ERROR ("matrix must be square to compute eigenvalues", GSL_ENOTSQR);
  95.     }
  96.   else if (eval->size != A->size1)
  97.     {
  98.       GSL_ERROR ("eigenvalue vector must match matrix size", GSL_EBADLEN);
  99.     }
  100.   else
  101.     {
  102.       const size_t N = A->size1;
  103.       double *const d = w->d;
  104.       double *const sd = w->sd;
  105.  
  106.       size_t a, b;
  107.  
  108.       /* handle special case */
  109.  
  110.       if (N == 1)
  111.     {
  112.       gsl_complex A00 = gsl_matrix_complex_get (A, 0, 0);
  113.       gsl_vector_set (eval, 0, GSL_REAL(A00));
  114.       return GSL_SUCCESS;
  115.     }
  116.  
  117.       {
  118.     gsl_vector_view d_vec = gsl_vector_view_array (d, N);
  119.     gsl_vector_view sd_vec = gsl_vector_view_array (sd, N - 1);
  120.     gsl_vector_complex_view tau_vec = gsl_vector_complex_view_array (w->tau, N-1);
  121.     gsl_linalg_hermtd_decomp (A, &tau_vec.vector);
  122.     gsl_linalg_hermtd_unpack_T (A, &d_vec.vector, &sd_vec.vector);
  123.       }
  124.  
  125.       /* Make an initial pass through the tridiagonal decomposition
  126.          to remove off-diagonal elements which are effectively zero */
  127.       
  128.       chop_small_elements (N, d, sd);
  129.       
  130.       /* Progressively reduce the matrix until it is diagonal */
  131.       
  132.       b = N - 1;
  133.       
  134.       while (b > 0)
  135.         {
  136.           if (sd[b - 1] == 0.0)
  137.             {
  138.               b--;
  139.               continue;
  140.             }
  141.           
  142.           /* Find the largest unreduced block (a,b) starting from b
  143.              and working backwards */
  144.           
  145.           a = b - 1;
  146.           
  147.           while (a > 0)
  148.             {
  149.               if (sd[a - 1] == 0.0)
  150.                 {
  151.                   break;
  152.                 }
  153.               a--;
  154.             }
  155.           
  156.           {
  157.             const size_t n_block = b - a + 1;
  158.             double *d_block = d + a;
  159.             double *sd_block = sd + a;
  160.             
  161.             /* apply QR reduction with implicit deflation to the
  162.                unreduced block */
  163.             
  164.             qrstep (n_block, d_block, sd_block, NULL, NULL);
  165.             
  166.             /* remove any small off-diagonal elements */
  167.             
  168.             chop_small_elements (n_block, d_block, sd_block);
  169.           }
  170.         }
  171.       
  172.       {
  173.         gsl_vector_view d_vec = gsl_vector_view_array (d, N);
  174.         gsl_vector_memcpy (eval, &d_vec.vector);
  175.       }
  176.       
  177.       return GSL_SUCCESS;
  178.     }
  179. }
  180.  
  181.  
  182.